不可变对象

概述

不可变对象一经安全发布，它就是不可变的。

需满足的条件

对象创建后其状态不能被修改；
对象所有的域都是final类型；
对象是正确创建的（在对象创建期间，其this引用未逸出）；
其中可以采用的方式包括：
1. 将类声明为final，不可被继承；
2. 将所有的成员声明为私有的，不允许直接访问其私有成员；
3. 对变量不向外提供set方法；
4. 将所有成员也声明为final，只能赋值一次；
5. 通过构造器初始化所有成员，进行深度拷贝;
6. 在get方法中，不直接返回对象本身，而是克隆对象，并返回对象的拷贝。

final关键字

可以用来修饰类、方法、变量。

修饰类：该类不能被继承：如Java中的String、Integer、Long等基础类型的封装类均是。

final类中的成员变量可根据需要设定为final。
final类中的方法均会被隐式指为final方法。

修饰方法：场景如下

锁定方法不会被继承类修改；
效率：在早期的Java实现版本中，会将final方法转为内嵌调用；但若final方法过大，反而拉低效率。
一个类的private方法会被隐式地指为final方法。

修饰变量：

若修饰基础数据类型：一旦初始化就不再更改。
若修饰引用类型：一旦初始化之后就不能再指向另一个对象。但可以修改其中的值。（好吧，这是废话… ）

@Slf4j
@NotThreadSafe  //非线程安全
public class ImmutableExample1 {

    private final static Integer a = 1;
    private final static String b = "2";
    private final static Map<Integer, Integer> map = Maps.newHashMap();

    static {
        map.put(1, 2);
        map.put(3, 4);
        map.put(5, 6);
    }

    public static void main(String[] args) {

        map.put(1, 3);
        log.info("{}", map.get(1));
    }

    private void test(final int a) {
    }
}

Collections.unmodifiableXXX方法

其中XXX可以是Collection、List、Set、Map等
相应的可以通过传入对应的数据类型作为参数传入方法，即可变为不可变对象。

看一个例子：

@Slf4j
@ThreadSafe
public class ImmutableExample2 {

    private static Map<Integer, Integer> map = Maps.newHashMap();

    static {
        map.put(1, 2);
        map.put(3, 4);
        map.put(5, 6);
        //调用unmodifiableMap方法
        map = Collections.unmodifiableMap(map);
    }

    public static void main(String[] args) {
        map.put(1, 3);
        log.info("{}", map.get(1));
    }

}

Guava的ImmutableXXX类

相似的，其中XXX可以是Collection、List、Set、Map等
这些类都提供了带初始化数据的声明方法，一旦初始化完成就成不可变对象了。

@ThreadSafe
public class ImmutableExample3 {

    private final static ImmutableList<Integer> list = ImmutableList.of(1, 2, 3);

    private final static ImmutableSet set = ImmutableSet.copyOf(list);

    private final static ImmutableMap<Integer, Integer> map = ImmutableMap.of(1, 2, 3, 4);


    private final static ImmutableMap<Integer, Integer> map2 = ImmutableMap.<Integer, Integer>builder()
            .put(1, 2).put(3, 4).put(5, 6).build();

    public static void main(String[] args) {
        System.out.println(map2.get(3));
    }

运行结果：4

例子分析：

ImmutableList通过of(a,b,c,xxxx)方法来填充数据，其中的数据为初始化的数据。
copyOf(xx)方法直接拷贝其他集合中数据。
通过builder().put(a, b)..put(x, x).(...).build()不停put(x,x)填充数据。

2 线程封闭

概述

线程封闭是一种较为简单的线程并发的方法。它其实把对象封装到一个线程里，该对象只对该线程是可见的。当然也就是线程安全的了。

实现线程封闭的方法

Ad-hoc 线程封闭：依赖程序控制实现，脆弱，是最糟糕的一种方式，不推荐！
堆栈封闭：应用广泛，依靠各线程局部变量的堆栈拷贝副本实现，无并发问题。避免使用全局变量。
数据库连接对应JDBC的Connection对象。
ThreadLocal线程封闭：实现较好，效率较高。（以后会做源码分析……）

ThreadLocal测试例子

RequestHolder.java

public class RequestHolder {

    private final static ThreadLocal<Long> requestHolder = new ThreadLocal<>();

    public static void add(Long id) {
        requestHolder.set(id);
    }

    public static Long getId() {
        return requestHolder.get();
    }

    public static void remove() {
        requestHolder.remove();
    }
}

方法分析：

该类存放需要绑定的信息。
其中add操作是在请求进入后端服务器，但还未进行实际处理时，调用该方法，写入相关信息。（通过filter：先拦截对应的URL，当前台访问该URL时，将相关信息写入ThreadLocal中；当URL实际被处理时，可直接从ThreadLocal中取出信息）。
定义移除方法，防止内存泄漏。在接口处理完之后进行处理（通过intercepter实现）。

HttpFilter.java

@Slf4j
public class HttpFilter implements Filter {
    @Override
    public void init(FilterConfig filterConfig) throws ServletException {

    }

    //核心方法
    @Override
    public void doFilter(ServletRequest servletRequest, ServletResponse servletResponse, FilterChain filterChain) throws IOException, ServletException {
        HttpServletRequest request = (HttpServletRequest) servletRequest;

        log.info("do filter, {}, {}", Thread.currentThread().getId(), request.getServletPath());

        RequestHolder.add(Thread.currentThread().getId());
        filterChain.doFilter(servletRequest, servletResponse);
    }

    //销毁
    @Override
    public void destroy() {

    }
}

方法分析：

因为是通过http请求，ServletRequest需转换为HttpServletRequest类型。
在RequestHolder中放入URL相关信息。
最后若该filter不是想拦截住该请求，只是做相关的数据处理，还想让其他过滤器接收到，则需最后调用filterChain.doFilter(servletRequest, servletResponse)。

HttpInterceptor.java

@Slf4j
public class HttpInterceptor extends HandlerInterceptorAdapter {

    //在处理之前输出
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
        log.info("preHandle");
        return true;
    }

    //在完成之后删除信息、输出日志
    @Override
    public void afterCompletion(HttpServletRequest request, HttpServletResponse response, Object handler, Exception ex) throws Exception {
        RequestHolder.remove();
        log.info("afterCompletion");
        return;
    }
}

ThreadLocalController.java

@Controller
@RequestMapping("/threadlocal")
public class ThreadLocalController {

    @RequestMapping("/test")
    @ResponseBody
    public Long test() {
        return RequestHolder.getId();
    }
}

ConcurrencyApplication.java

true//使用springboot快速进行测试
@SpringBootApplication
public class ConcurrencyApplication extends WebMvcConfigurerAdapter {

truepublic static void main(String[] args) {
truetrueSpringApplication.run(ConcurrencyApplication.class, args);
true}

true@Bean
truepublic FilterRegistrationBean httpFilter() {
truetrueFilterRegistrationBean registrationBean = new FilterRegistrationBean();
truetrueregistrationBean.setFilter(new HttpFilter());

truetrueregistrationBean.addUrlPatterns("/threadlocal/*");
truetruereturn registrationBean;
true}

true@Override
truepublic void addInterceptors(InterceptorRegistry registry) {

truetrueregistry.addInterceptor(new HttpInterceptor()).addPathPatterns("/**");
true}
}

方法分析：

通过springboot创建registrationBean并指定过滤URL类型为”/threadlocal/*”。
重写addInterceptors -> 添加拦截器，并指定拦截的路径类型。
ThreadLocalController.java中指定请求映射的名称和返回内容。

接口测试结果：(使用Postman进行接口测试)

日志部分截图：

可以看出例子是和日志完全对应的。
重复一下threadlocal的实现思想：当一个请求进来时，通过过滤器Filter，将数据信息（这里是线程id）存储到threadlocal中，当接口被调用处理时，可以直接从中取出来；当接口处理完成，通过拦截器Interceptor的afterCompletion把当前线程中的数据信息（这里是线程id）移除，避免内存泄漏。

1、什么是线程封闭？

它其实就是把对象封装到一个线程里，只有一个线程能看到这个对象，那么这个对象就算不是线程安全的，也不会出现任何线程安全方面的问题。

线程封闭技术有一个常见的应用：

数据库连接对应jdbc的Connection对象，Connection对象在实现的时候并没有对线程安全做太多的处理，jdbc的规范里也没有要求Connection对象必须是线程安全的。
实际在服务器应用程序中，线程从连接池获取了一个Connection对象，使用完再把Connection对象返回给连接池，由于大多数请求都是由单线程采用同步的方式来处理的，并且在Connection对象返回之前，连接池不会将它分配给其他线程。因此这种连接管理模式处理请求时隐含的将Connection对象封闭在线程里面，这样我们使用的connection对象虽然本身不是线程安全的，但是它通过线程封闭也做到了线程安全。
2、线程封闭的种类：

（1）Ad-hoc 线程封闭：

Ad-hoc线程封闭是指，维护线程封闭性的职责完全由程序实现来承担。Ad-hoc线程封闭是非常脆弱的，因为没有任何一种语言特性，例如可见性修饰符或局部变量，能将对象封闭到目标线程上。事实上，对线程封闭对象（例如，GUI应用程序中的可视化组件或数据模型等）的引用通常保存在公有变量中。

（2）堆栈封闭：
堆栈封闭其实就是方法中定义局部变量。不存在并发问题。多个线程访问一个方法的时候，方法中的局部变量都会被拷贝一份到线程的栈中（Java内存模型），所以局部变量是不会被多个线程所共享的。

（3）ThreadLocal线程封闭：

它是一个特别好的封闭方法，其实ThreadLocal内部维护了一个map,map的key是每个线程的名称，而map的value就是我们要封闭的对象。ThreadLocal提供了get、set、remove方法，每个操作都是基于当前线程的，所以它是线程安全的。

//ThreadLocal的get方法源码
public T get() {
    Thread t = Thread.currentThread();//当前线程对象
    ThreadLocalMap map = getMap(t);//get操作基于当前线程
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    return setInitialValue();
}

3、Springboot框架中使用ThreadLocal

Coding：
（1）创建一个包含ThreadLocal对象的类，并提供基础的添加、删除、获取操作。

public class RequestHolder {

    private final static ThreadLocal<Long> requestHolder = new ThreadLocal<>();

    public static void add(Long id) {
        requestHolder.set(id);
    }

    public static Long getId() {
        return requestHolder.get();
    }

    public static void remove() {
        requestHolder.remove();
    }
}

（2）创建Filter，在Filter中对ThreadLocal做添加操作。

public class HttpFilter implements Filter {

    @Override
    public void init(FilterConfig filterConfig) throws ServletException {

    }

    @Override
    public void doFilter(ServletRequest servletRequest,
                         ServletResponse servletResponse,
                         FilterChain filterChain) throws IOException, ServletException {
        HttpServletRequest request = (HttpServletRequest) servletRequest;
        //打印当前线程的ID与请求路径
        log.info("do filter, {}, {}", Thread.currentThread().getId(), request.getServletPath());
        //将当前线程ID添加到ThreadLocal中
        RequestHolder.add(Thread.currentThread().getId());
        filterChain.doFilter(servletRequest, servletResponse);
    }

    @Override
    public void destroy() {

    }
}

(3)创建controller，在controller中获取到filter中存入的值

@Controller
@RequestMapping("/threadLocal")
public class ThreadLocalController {

    @RequestMapping("/test")
    @ResponseBody
    public Long test() {
        return RequestHolder.getId();
    }
}

（4）创建拦截器Interceptor，在拦截器中删除刚才添加的值

public class HttpInterceptor extends HandlerInterceptorAdapter {

    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response,
                             Object handler) throws Exception {
        log.info("preHandle");
        return true;
    }

    @Override
    public void afterCompletion(HttpServletRequest request, HttpServletResponse response, 
                            Object handler, Exception ex) throws Exception {
        RequestHolder.remove();
        log.info("afterCompletion");
        return;
    }
}

（5）在springboot的启动类Application中注册filter与Interceptor。要继承WebMvcConfigurerAdapter 类。（我这里的启动类名为：ConcurrencyApplication）

@SpringBootApplication
public class ConcurrencyApplication extends WebMvcConfigurerAdapter {

    public static void main(String[] args) {
        SpringApplication.run(ConcurrencyApplication.class, args);
    }

    //注册过滤器
    @Bean
    public FilterRegistrationBean httpFilter() {
        FilterRegistrationBean registrationBean = new FilterRegistrationBean();
        registrationBean.setFilter(new HttpFilter());
        //设置要过滤的url
        registrationBean.addUrlPatterns("/threadLocal/*");
        return registrationBean;
    }

    //注册拦截器
    @Override
    public void addInterceptors(InterceptorRegistry registry) {
        registry.addInterceptor(new HttpInterceptor()).addPathPatterns("/**");
    }
}

（6）运行程序，访问 http://localhost:8080/threadLocal/test 结果如下

从控制台的打印日志我们可以看出，首先filter过滤器先获取到我们当前的线程ID为40、我们当前的请求路径为/threadLocal/test ，紧接着进入了我们的Interceptor的preHandle方法中，打印了preHandle字样。最后进入了我们的Interceptor的afterCompletion方法，删除了我们之前存入的值，并打印了afterCompletion字样。

3 线程不安全类与写法

概述

线程不安全类：如果一个类的对象同时被多个线程访问，若不做相应的同步或并发处理，容易出现线程不安全的现象，比如：抛出异常、逻辑处理错误等。

StringBiulder

看一个例子：（借助之前的例子结构）

@Slf4j
@NotThreadSafe
public class StringExample1 {

    public static int clientTotal = 5000;

    public static int threadTotal = 200;

    public static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws Exception {
        ExecutorService executorService = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(threadTotal);
        final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
        for (int i = 0; i < clientTotal ; i++) {
            executorService.execute(() -> {
                try {
                    semaphore.acquire();
                    update();
                    semaphore.release();
                } catch (Exception e) {
                    log.error("exception", e);
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        executorService.shutdown();
        log.info("size:{}", stringBuilder.length());
    }

    private static void update() {
        stringBuilder.append("1");
    }
}

结果分析：

多次运行，结果几乎未达5000，显然StringBuilder是非线程安全的。
通过定义stringBuilder对象，核心方法为update() -> 每次拼接一个字符串，最后取其长度length。

StringBuffer

例子代码结构跟上面一样，只需将StringBiulder换为StringBuffer，且其两者方法名相同。

运行结果：
多次运行，结果均为5000。StringBuffer是线程安全的！查看StringBuffer源码

@Override
public synchronized StringBuffer append(String str) {
    toStringCache = null;
    super.append(str);
    return this;
}

public final class StringBuffer
   extends AbstractStringBuilder
   implements java.io.Serializable, CharSequence{XXX省略}
@Override
public synchronized String toString() {
    if (toStringCache == null) {
        toStringCache = Arrays.copyOfRange(value, 0, count);
    }
    return new String(toStringCache, true);
}

源码分析：

几乎所有复写的方法都有toStringCache变量。为对象方便转为String类型的字段，调用Arrays.copyOfRange(value, 0, count)，return new String(toStringCache, true)：其中该构造方法是String包私有的构造方法，以确保数值分享的效率。
StringBuffer继承自AbstractStringBuilder，并几乎重写了所有继承来的方法。调用父辈super的append方法，即AbstractStringBuilder的方法。且StringBuffer对象一经修改，toStringCache清空为null。类似String包装类的对象，避免多线程并发问题。（以后细说String包装类…）
为了线程安全，几乎所有复写的方法都用synchronized进行标识，即使效率较低。
StringBiulder性能好，但不适用于多线程。但适用于场景为方法内的局部变量操作（上篇线程封闭的手记中说到：隐式的堆栈封闭），线程安全且性能较好。

SimpleDateFormate

Java提供的供日期转换的类。该例子结构仍然和上述例子相同。只需定义一个simpleDateFormat实例，核心方法换为parse（xxx:日期语句）

运行结果：
出现异常：parse exception -- java.lang.NumberFormatException: multiple points
非常简单，说明了该日期转换方法是非线程间安全的。

正确写法：（通过堆栈封闭->声明为核心方法内的局部变量，即每次声明一个新的对象进行调用）

仍然是之前的测试结构，但还是贴出来看看吧。

> @Slf4j
> @ThreadSafe
> public class DateFormatExample2 {
> 
>     // 请求总数
>     public static int clientTotal = 5000;
> 
>     // 同时并发执行的线程数
>     public static int threadTotal = 200;
> 
>     public static void main(String[] args) throws Exception {
>         ExecutorService executorService = Executors.newCachedThreadPool();
>         final Semaphore semaphore = new Semaphore(threadTotal);
>         final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
>         for (int i = 0; i < clientTotal ; i++) {
>             executorService.execute(() -> {
>                 try {
>                     semaphore.acquire();
>                     update();
>                     semaphore.release();
>                 } catch (Exception e) {
>                     log.error("exception", e);
>                 }
>                 countDownLatch.countDown();
>             });
>         }
>         countDownLatch.await();
>         executorService.shutdown();
>     }
> 
>     private static void update() {
>         try {
>             SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyyMMdd");
>             simpleDateFormat.parse("20180208");
>         } catch (Exception e) {
>             log.error("parse exception", e);
>         }
>     }
> }
>

运行结果： 多次运行，不会报错！是线程安全！

Joda Time

该类本质上并不属于Java提供。需引入jar包。例子仍然是之前的测试结构。只不过日志输出了次数及当时日期
1
2
3
4
5
> private static void update(int i) {
>     //转换完后DateTime，调用toDate()转为Date对象。
>     log.info("{}, {}", i == 4999 ? i+"--------------------------" : i, DateTime.parse("20180728", dateTimeFormatter).toDate());
> }
>

运行结果：

1
2
3

由于调用是多并发的，调用次序是乱序，但总数一定！

  由于i是从0到4999，即当i = 4999时说明已运行慢5000个，即线程安全！

Collections部分

一般情况下，我们使用ArrayList、HashSet、HashMap是在方法中定义局部变量，此时由于堆栈封闭的特性，自然不会有线程安全问题。但是，当将其定义为静态域中，且未做线程安全措施时，极有可能会导致多线程并发错误。

由于该三个集合是Java中最常见的、最重要的集合，此处仅分析说明是非线程安全的类。其详细内容我会另起手记再做说明！！

ArrayList

弄个例子：(还是之前的框架)

@Slf4j
@NotThreadSafe
public class ArrayListExample {

    public static int clientTotal = 5000;
    public static int threadTotal = 200;

    private static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        ExecutorService executorService = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(threadTotal);
        final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
        for (int i = 0; i < clientTotal; i++) {
            final int count = i;
            executorService.execute(() -> {
                try {
                    semaphore.acquire();
                    update(count);
                    semaphore.release();
                } catch (Exception e) {
                    log.error("exception", e);
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        executorService.shutdown();
        log.info("size:{}", list.size());
    }
    private static void update(int i) { list.add(i); }
}

运行结果：

1	13:31:39.296 [main] INFO com.mmall.concurrency.commonUnsafe.ArrayListExample - size:4986

显而易见，是非线程安全的。

HashSet

同理，HashSet同样进行测试，结果表明同样是非线程安全的！

HashMap

同理，HashMap同样进行测试，结果表明同样是非线程安全的！

线程不安全的写法

先检查再执行：

if (aaaa)
{
  bbbbbbbbb;
}

这个较易解释，在之前说AtomicXXX时说过：
在多线程并发时，可能多个线程执行到if语句的判断，且同时符合，然后分别作出修改。即该操作的原子性不能得到保证！故当有多线程并发问题时，考虑清楚，加锁进行处理。

3.2 线程不安全的类

如果一个类的对象同时可以被多个线程访问，并且你不做特殊的同步或并发处理，那么它就很容易表现出线程不安全的现象。比如抛出异常、逻辑处理错误…
下面列举一下常见的线程不安全的类及对应的线程安全类：

（1）StringBuilder 与 StringBuffer

StringBuilder是线程不安全的，而StringBuffer是线程安全的。分析源码：StringBuffer的方法使用了synchronized关键字修饰。

@Override
    public synchronized StringBuffer append(String str) {
        toStringCache = null;
        super.append(str);
        return this;
    }

SimpleDateFormat 与 jodatime插件

SimpleDateFormat 类在处理时间的时候，如下写法是线程不安全的：

private static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyyMMdd");

//线程调用方法
private static void update() {
    try {
        simpleDateFormat.parse("20180208");
    } catch (Exception e) {
        log.error("parse exception", e);
    }
}

但是我们可以变换其为线程安全的写法：在每次转换的时候使用线程封闭，新建变量

private static void update() {
    try {
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyyMMdd");
        simpleDateFormat.parse("20180208");
    } catch (Exception e) {
        log.error("parse exception", e);
    }
}

另外我们也可以使用jodatime插件来转换时间：其可以保证线程安全性
Joda 类具有不可变性，因此它们的实例无法被修改。（不可变类的一个优点就是它们是线程安全的）

private static DateTimeFormatter dateTimeFormatter = DateTimeFormat.forPattern("yyyyMMdd");

private static void update(int i) {
    log.info("{}, {}", i, DateTime.parse("20180208", dateTimeFormatter).toDate());
}

ArrayList,HashSet,HashMap 等Collection类

像ArrayList,HashSet,HashMap 等Collection类均是线程不安全的，我们以ArrayList举例分析一下源码：
1、ArrayList的基本属性：

## 在声明时使用了transient 关键字，此关键字意为在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。而ArrayList实现了序列化接口，自己定义了序列化方法（在此不描述）。

//对象数组：ArrayList的底层数据结构
private transient Object[] elementData;
//elementData中已存放的元素的个数
private int size;
//默认数组容量
private static final int DEFAULT_CAPACITY = 10;

2、初始化

/**

- 创建一个容量为initialCapacity的空的（size==0）对象数组
  */
   public ArrayList(int initialCapacity) {
  super();//即父类protected AbstractList() {}
  if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal Capacity:" + initialCapacity);
  this.elementData = new Object[initialCapacity];
  }

/**

- 默认初始化一个容量为10的对象数组
  */
   public ArrayList() {
  this(10);
   }

3、添加方法（重点）

//每次添加时将数组扩容1，然后再赋值
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

4、总结：ArrayList每次对内容进行插入操作的时候，都会做扩容处理，这是ArrayList的优点（无容量的限制），同时也是缺点，线程不安全。（以下例子取材于鱼笑笑博客）
一个 ArrayList ，在添加一个元素的时候，它可能会有两步来完成：

在 Items[Size] 的位置存放此元素；
增大 Size 的值。
在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；
而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。那好，现在我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。

那么如何将其处理为线程安全的？或者说对应的线程安全类有哪些呢？接下来就涉及到我们同步容器

4-1同步容器

同步容器分两类，一种是Java提供好的类，另一类是Collections类中的相关同步方法。

（1）ArrayList的线程安全类：Vector,Stack

Vector实现了List接口，Vector实际上就是一个数组，和ArrayList非常的类似，但是内部的方法都是使用synchronized修饰过的方法。
Stack它的方法也是使用synchronized修饰了，继承了Vector，实际上就是栈
使用举例（Vector）：

//定义
private static List<Integer> list = new Vector<>();
//多线程调用方法
private static void update(int i) {
   list.add(i);
}

源码分析：使用了synchronized修饰

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

但是Vector也不是完全的线程安全的，比如：
错误[1]：删除与获取并发操作

public class VectorExample {

    private static Vector<Integer> vector = new Vector<>();

    public static void main(String[] args) {

        while (true) {
            for (int i = 0; i < 10; i++) {
                vector.add(i);
            }
            Thread thread1 = new Thread() {
                public void run() {
                    for (int i = 0; i < vector.size(); i++) {
                        vector.remove(i);
                    }
                }
            };
            Thread thread2 = new Thread() {
                public void run() {
                    for (int i = 0; i < vector.size(); i++) {
                        vector.get(i);
                    }
                }
            };
            thread1.start();
            thread2.start();
        }
    }
}

运行结果：报错java.lang.ArrayIndexOutOfBoundsException: Array index out of range

## 原因分析：同时发生获取与删除的操作。当两个线程在同一时间都判断了vector的size，假设都判断为9，而下一刻线程1执行了remove操作，随后线程2才去get，所以就出现了错误。synchronized关键字可以保证同一时间只有一个线程执行该方法，但是多个线程同时分别执行remove、add、get操作的时候就无法控制了。

错误[2]：使用foreach\iterator遍历Vector的时候进行增删操作

public class VectorExample3 {

    // 报错java.util.ConcurrentModificationException
    private static void test1(Vector<Integer> v1) { // foreach
        for(Integer i : v1) {
            if (i.equals(3)) {
                v1.remove(i);
            }
        }
    }

    // 报错java.util.ConcurrentModificationException
    private static void test2(Vector<Integer> v1) { // iterator
        Iterator<Integer> iterator = v1.iterator();
        while (iterator.hasNext()) {
            Integer i = iterator.next();
            if (i.equals(3)) {
                v1.remove(i);
            }
        }
    }

    // success
    private static void test3(Vector<Integer> v1) { // for
        for (int i = 0; i < v1.size(); i++) {
            if (v1.get(i).equals(3)) {
                v1.remove(i);
            }
        }
    }

    public static void main(String[] args) {
        Vector<Integer> vector = new Vector<>();
        vector.add(1);
        vector.add(2);
        vector.add(3);
        test1(vector);
    }
}

2）HashMap的线程安全类：HashTable

//定义
private static Map<Integer, Integer> map = new Hashtable<>();
//多线程调用方法
private static void update(int i) {
    map.put(i, i);
}

源码分析：

保证安全性：使用了synchronized修饰
不允许空值（在代码中特殊做了判断）

HashMap和HashTable都使用哈希表来存储键值对。在数据结构上是基本相同的，都创建了一个继承自Map.Entry的私有的内部类Entry，每一个Entry对象表示存储在哈希表中的一个键值对。

Entry对象唯一表示一个键值对，有四个属性：
-K key 键对象
-V value 值对象
-int hash 键对象的hash值
-Entry entry 指向链表中下一个Entry对象，可为null，表示当前Entry对象在链表尾部

public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
    if ((entry.hash == hash) && entry.key.equals(key)) {
        V old = entry.value;
        entry.value = value;
        return old;
    }
}

addEntry(hash, key, value, index);
return null;

（3）Collections类中的相关同步方法

Collections类中提供了一系列的线程安全方法用于处理ArrayList等线程不安全的Collection类

使用方法：

//定义

private static List<Integer> list = Collections.synchronizedList(Lists.newArrayList());
//多线程调用方法
private static void update(int i) {
    list.add(i);

## }

源码分析：
内部操作的方法使用了synchronized修饰符

static class SynchronizedList<E>
       extends SynchronizedCollection<E>
       implements List<E> {
       ...
       public E get(int index) {
           synchronized (mutex) {return list.get(index);}
       }
       public E set(int index, E element) {
           synchronized (mutex) {return list.set(index, element);}
       }
       public void add(int index, E element) {
           synchronized (mutex) {list.add(index, element);}
       }
       public E remove(int index) {
           synchronized (mutex) {return list.remove(index);}
       }
       ...
}

4-2 同步容器

本节内容不仅丰富而且十分有趣实用~

概述

同步容器大致分为两类：

由List发展来的Vector、Stack；由HashMap发展来的HashTable（其中K,V均不能为null）

Collections工具类提供的静态工厂方法 –> 均为synchronizedXXXX(List/Set/Map)的模样。

看个例子：(好吧，这个测试的框架都快看恶心了ORZ)

@Slf4j
@ThreadSafe
public class VectorExample1 {
    public static int clientTotal = 5000;
    public static int threadTotal = 200;

    private static List<Integer> list = new Vector<>();

    public static void main(String[] args) throws Exception {
        ExecutorService executorService = Executors.newCachedThreadPool();
        final Semaphore semaphore = new Semaphore(threadTotal);
        final CountDownLatch countDownLatch = new CountDownLatch(clientTotal);
        for (int i = 0; i < clientTotal; i++) {
            final int count = i;
            executorService.execute(() -> {
                try {
                    semaphore.acquire();
                    update(count);
                    semaphore.release();
                } catch (Exception e) {
                    log.error("exception", e);
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        executorService.shutdown();
        log.info("size:{}", list.size());
    }
    private static void update(int i) {list.add(i);}
}

运行结果：

1	14:10:04.044 [main] INFO com.mmall.concurrency.syncContainer.VectorExample1 - size:5000

看一下Vector的源码:

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

其他方法同理，基本都使用synchronized进行标识。
但是！！
同步容器不一定就是线程安全的！

再看例子：

@NotThreadSafe
public class VectorExample2 {

    private static Vector<Integer> vector = new Vector<>();

    public static void main(String[] args) {

        while (true) {

            for (int i = 0; i < 10; i++) {
                vector.add(i);
            }

            Thread thread1 = new Thread() {
                public void run() {
                    for (int i = 0; i < vector.size(); i++) {
                        vector.remove(i);
                    }
                }
            };

            Thread thread2 = new Thread() {
                public void run() {
                    for (int i = 0; i < vector.size(); i++) {
                        vector.get(i);
                    }
                }
            };
            thread1.start();
            thread2.start();
        }
    }
}

运行结果：

既然Vector的remove和get方法都抛出ArrayIndexOutOfBoundsException异常，那看一下源码吧：

/**
 * Returns the element at the specified position in this Vector.
 *
 * @param index index of the element to return
 * @return object at the specified index
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *            ({@code index < 0 || index >= size()})
 * @since 1.2
 */
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

源码分析：

get方法出现该异常一定是remove方法造成的。
数组越界情况为：index < 0 或 index >= size()。但既然是remove方法，那应该只能是index小于0或index不存在的情况了。
同步容器不一定就能保证线程并发安全。

例子情况分析：（常见的多线程间执行顺序的差异导致）
在其中的for循环中，当一个线程调用get方法时（其中其下标设为i），另一个线程恰好在前一时刻调用了remove方法（恰好其下标也是i），此时下标为i的数据已经不存在，便抛出ArrayIndexOutOfBoundsException异常。

再来看一个Vector的测试例子：

public class VectorExample3 {
    private static void test1(Vector<Integer> v1) { // foreach
        for(Integer i : v1) {
            if (i.equals(3)) {
                v1.remove(i);
            }
        }
    }
    // java.util.ConcurrentModificationException
    private static void test2(Vector<Integer> v1) { // iterator
        Iterator<Integer> iterator = v1.iterator();
        while (iterator.hasNext()) {
            Integer i = iterator.next();
            if (i.equals(3)) {
                v1.remove(i);
            }
        }
    }
    // success
    private static void test3(Vector<Integer> v1) { // for
        for (int i = 0; i < v1.size(); i++) {
            if (v1.get(i).equals(3)) {
                v1.remove(i);
            }
        }
    }

    public static void main(String[] args) {

        Vector<Integer> vector = new Vector<>();
        vector.add(1);
        vector.add(2);
        vector.add(3);
        test1(vector);
    }
}

运行结果：

main函数执行test1(vector)时，抛出java.util.ConcurrentModificationException；
main函数执行test2(vector)时，抛出java.util.ConcurrentModificationException；
main函数执行test3(vector)时，程序正常结束。

结果分析：
使用迭代器iterator或foreach循环（加强版for循环）会抛出并发修改异常；但一般for语句正常结束。

废话不多说，看源码：

public E next() {
    synchronized (Vector.this) {
        checkForComodification();
        int i = cursor;
        if (i >= elementCount)
            throw new NoSuchElementException();
        cursor = i + 1;
        return elementData(lastRet = i);
    }
}

public void remove() {
    if (lastRet == -1)
        throw new IllegalStateException();
    synchronized (Vector.this) {
        checkForComodification();
        Vector.this.remove(lastRet);
        expectedModCount = modCount;
    }
    cursor = lastRet;
    lastRet = -1;
}
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

源码分析：
由于迭代器iterator或foreach循环中的remove操作使得modCount != expectedModCount，即修改后的count与期望的count不一致，定是并发过程中Vector被修改；但for循环每次循环都会重新计算i,此时Vector已被更新……（好吧，我承认，我其实这里还是不太懂，for循环这里只是我的猜想。）
解决方案：
在讯循环中不要进行修改操作：

先查，若有需要进行修改的对象，则做上标记
循环之后进行修改

当使用迭代器iterator迭代时，使用synchronized或Lock做同步措施（也可以使用并发容器copyOnWriteArrayList等代替ArrayList或Vector）

Stack

继承了Vector，其两者用法基本一致。只不过它是一个LIFO的数据结构。

HashTable

好吧，其实用的还是那套框架，换一下实例声明的名字就行了。

运行结果：

1	15:05:24.433 [main] INFO com.mmall.concurrency.syncContainer.HashTableExample - size:5000

既然是线程安全的，再看一下源码：

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

好吧，还是synchronized标识修饰方法。故HashTable是一个线程安全的同步容器。

Collections工具类方法

synchronizedList

例子：（还是原来的配方，还是熟悉的测试框架…不过实例声明换成Collections的方法）

1	private static List<Integer> list = Collections.synchronizedList(Lists.newArrayList());

好吧，非常不幸的告诉你，它的运行结果还是:

1	15:20:49.641 [main] INFO com.mmall.concurrency.syncContainer.CollectionsExample1 - size:5000

不管怎样，来都来了，那看一下源码：（没错，注释已经“入党”，已经自动汉化了）

/ **
     *返回由指定的支持的同步（线程安全）列表
     *清单。为了保证串行访问，至关重要的是
     * <strong>所有</ strong>对支持列表的访问权限已完成
     *通过返回的列表。<p>
     *
     *用户必须手动地同步返回的内容
     *迭代时列出：
     * <pre>
     * List list = Collections.synchronizedList（new ArrayList（））;
     * ......
     * synchronized（list）{
     * Iterator i = list.iterator（）; //必须在同步块中
     * while（i.hasNext（））
     * foo（i.next（））;
     *}
     * </ pre>
     *不遵循此建议可能会导致非确定性行为。
     *
     * <p>如果指定的列表是，则返回的列表将是可序列化的
     *可序列化。
     *
     * @param <T>列表中对象的类
     * @param列出要在同步列表中“包装”的列表。
     * @return指定列表的同步视图。
     * /
    public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
    }

注意到，这竟然还有SynchronizedRandomAccessList和SynchronizedList之分？

static class SynchronizedRandomAccessList<E>
    extends SynchronizedList<E>
    implements RandomAccess {

    SynchronizedRandomAccessList(List<E> list) {
        super(list);
    }
    .
    .
    .
  }

可知SynchronizedRandomAccessList继承SynchronizedList，并实现了RandomAccess接口。
那这接口是什么鬼？

1 2	public interface RandomAccess { }

没了，他就只是个接口……

读者：求你了，看一下注释吧，老哥~
我：emmmm，行~~

> /**
>   * 标记接口被<tt> List </ tt>用来指示
>   *它们支持快速（通常是恒定时间）随机访问。
>   *此接口的首要目的是允许通用算法更改它们，
>   *当被应用于随机或顺序访问多个列表时，
>   *以提供良好性能
> */
>

读者：泥垢了！！~
我：emmmm

synchronizedSet

只是把上面的例子的实例换成Set罢了、、

synchronizedMap

只是把上面的例子的实例换Map罢了、、

4-3 并发容器及安全共享策略总结

概述

Java并发容器JUC是三个单词的缩写。是JDK下面的一个包名。即Java.util.concurrency。
上一节我们介绍了ArrayList、HashMap、HashSet对应的同步容器保证其线程安全，这节我们介绍一下其对应的并发容器。

ArrayList –> CopyOnWriteArrayList

CopyOnWriteArrayList 写操作时复制，当有新元素添加到集合中时，从原有的数组中拷贝一份出来，然后在新的数组上作写操作，将原来的数组指向新的数组。整个数组的add操作都是在锁的保护下进行的，防止并发时复制多份副本。读操作是在原数组中进行，不需要加锁

缺点：
1.写操作时复制消耗内存，如果元素比较多时候，容易导致young gc 和full gc。
2.不能用于实时读的场景.由于复制和add操作等需要时间，故读取时可能读到旧值。
能做到最终一致性，但无法满足实时性的要求，更适合读多写少的场景。
如果无法知道数组有多大，或者add,set操作有多少，慎用此类,在大量的复制副本的过程中很容易出错。

设计思想：
1.读写分离
2.最终一致性
3.使用时另外开辟空间，防止并发冲突

源码分析

//构造方法
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;//使用对象数组来承载数据
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

//添加数据方法
public boolean add(E e) {
    final ReentrantLock lock = this.lock;//使用重入锁，保证线程安全
    lock.lock();
    try {
        Object[] elements = getArray();//获取当前数组数据
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);//复制当前数组并且扩容+1
        newElements[len] = e;//将要添加的数据放入新数组
        setArray(newElements);//将原来的数组指向新的数组
        return true;
    } finally {
        lock.unlock();
    }
}

//获取数据方法，与普通的get没什么差别
private E get(Object[] a, int index) {
    return (E) a[index];
}

HashSet –> CopyOnWriteArraySetHashSet –> CopyOnWriteArraySet

它是线程安全的，底层实现使用的是CopyOnWriteArrayList，因此它也适用于大小很小的set集合，只读操作远大于可变操作。因为他需要copy整个数组，所以包括add、remove、set它的开销相对于大一些。
迭代器不支持可变的remove操作。使用迭代器遍历的时候速度很快，而且不会与其他线程发生冲突。
源码分析：

//构造方法
public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();//底层使用CopyOnWriteArrayList
}

//添加元素方法，基本实现原理与CopyOnWriteArrayList相同
private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {//添加了元素去重操作
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

####TreeSet –> ConcurrentSkipListSet

它是JDK6新增的类，同TreeSet一样支持自然排序，并且可以在构造的时候自己定义比较器。

同其他set集合，是基于map集合的（基于ConcurrentSkipListMap），在多线程环境下，里面的contains、add、remove操作都是线程安全的。
多个线程可以安全的并发的执行插入、移除、和访问操作。但是对于批量操作addAll、removeAll、retainAll和containsAll并不能保证以原子方式执行，原因是addAll、removeAll、retainAll底层调用的还是contains、add、remove方法，只能保证每一次的执行是原子性的，代表在单一执行操纵时不会被打断，但是不能保证每一次批量操作都不会被打断。在使用批量操作时，还是需要手动加上同步操作的。
不允许使用null元素的，它无法可靠的将参数及返回值与不存在的元素区分开来。
源码分析：
//构造方法

//构造方法
public ConcurrentSkipListSet() {
    m = new ConcurrentSkipListMap<E,Object>();//使用ConcurrentSkipListMap实现
}

HashMap –> ConcurrentHashMap

不允许空值，在实际的应用中除了少数的插入操作和删除操作外，绝大多数我们使用map都是读取操作。而且读操作大多数都是成功的。基于这个前提，它针对读操作做了大量的优化。因此这个类在高并发环境下有特别好的表现。
ConcurrentHashMap作为Concurrent一族，其有着高效地并发操作，相比Hashtable的笨重，ConcurrentHashMap则更胜一筹了。
在1.8版本以前，ConcurrentHashMap采用分段锁的概念，使锁更加细化，但是1.8已经改变了这种思路，而是利用CAS+Synchronized来保证并发更新的安全，当然底层采用数组+链表+红黑树的存储结构。
源码分析：推荐参考chenssy的博文：J.U.C之Java并发容器：ConcurrentHashMap
TreeMap –> ConcurrentSkipListMap

底层实现采用SkipList跳表
曾经有人用ConcurrentHashMap与ConcurrentSkipListMap做性能测试，在4个线程1.6W的数据条件下，前者的数据存取速度是后者的4倍左右。但是后者有几个前者不能比拟的优点：
1、Key是有序的
2、支持更高的并发，存储时间与线程数无关
安全共享对象策略

线程限制：一个被线程限制的对象，由线程独占，并且只能被占有它的线程修改
共享只读：一个共享只读的U帝乡，在没有额外同步的情况下，可以被多个线程并发访问，但是任何线程都不能修改它
线程安全对象：一个线程安全的对象或者容器，在内部通过同步机制来保障线程安全，多以其他线程无需额外的同步就可以通过公共接口随意访问他被守护对象：被守护对象只能通过获取特定的锁来访问。

copyOnWriteArrayList

线程写操作时复制，当有新元素添加到copyOnWriteArrayList时，它先从原有的数组中拷贝出一份，在新开辟出的新数组中写入，写完后再将原数组指向新数组。其操作都是在锁的域中，防止在多线程中复制出多个副本出来，导致原数组指向错误。

特点：

由于写操作需进行复制操作，耗用内存；当元素内容过多时，该复制操作会占用非常多的内存，导致minor-GC，甚至full-GC。
虽然最终会保持一致性，但不能用于实时读的操作。
读写分离，且适合读多写少的场景。
若add或set的数据不清楚或过多，要慎用！
读时不加锁，写时加锁。

1	private static List<Integer> list = new CopyOnWriteArrayList<>();

运行结果：

1	22:03:09.363 [main] INFO com.mmall.concurrency.concurrent.CopyOnWriteArrayListExample - size:5000

结果验证了该类为线程安全的！

看一下它的源码：

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

显然是使用重入锁进行操作加锁。add方法的实现与上面的说明对应！

copyOnWriteArraySet

对应于HashSet。

它的底层实现与copyOnWriteArrayList是一样的。特点也是一样的。当使用迭代器iterator迭代时，速度快效率高线程安全。

ConcurrentSkipListSet

对应于TreeSet。是JDK 1.6中新增的类，同样支持自然排序。在构造时可以自定义比较器。基于map集合，故而多线程并发环境下，它的类内插入、移除、访问方法都是线程安全的。但是对于批量操作，比如addAll()、removeAll()、retainAll()、containsAll并不能保证其操作的原子性。

例子就不用演示了，跟上面的例子方法几乎完全一样，运行结果也显示是线程安全的！批量操作时就不能保证线程安全了！需额外增加锁机制。

ConcurrentHashMap

对应于HashMap。其中需注意，key或Value不需为null。高并发环境中，表现较好。（后续会详细讲）

ConcurrentSkipListMap

对应于TreeMap。内部是使用SkipList即跳表的结构实现。

SkipList： 跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。推荐阅读

跳表性质：

由很多层结构组成；
每一层都是一个有序的链表；
最底层(Level 1)的链表包含所有元素；
如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现；
每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
推荐阅读

虽然ConcurrentSkipListMap的效率不及ConcurrentHashMap，但它也有ConcurrentHashMap不可比拟的优点：

ConcurrentSkipListMap中的key值是有序的。
支持更高的线程并发。其存取时间与线程数量是几乎没有关系的。即线程越多，越有利于ConcurrentSkipListMap的性能发挥。

上面介绍的几个例子就不进行例子演示了，均只是改变了变量的声明，其他内容仍然与原测试结构相同。